package week_04;

import javax.lang.model.util.Elements;

/**
 * 74. 搜索二维矩阵
 * <p>
 * 编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * <p>
 * 示例 2：
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SearchA2dMatrix {
    public boolean searchMatrix_1(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 暴力循环 从每行开始向前搜，超过就跳过，到下一行继续
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (target == matrix[i][j]) {
                    return true;
                } else if (matrix[i][j] > target) {
                    break;
                }
            }
        }
        return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        // 两次二分法查询 先后定位row,col
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0;
        int r = m - 1;
        int row = 0;
        while (l < r) {
            int mid = (r + l + 1) >> 1;
            if (matrix[mid][0] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        row = l;
        if (matrix[row][0] == target) return true;
        if (matrix[row][0] > target) return false;
        l = 0;
        r = n - 1;
        int col;
        while (l < r) {
            int mid = (r + l + 1) >> 1;
            if (matrix[row][mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        col = l;
        return matrix[row][col] == target;
    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        // 一次二分
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0;
        int r = m * n - 1;
        System.out.println(l + ":" + r);
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            System.out.println("l" + ":" + l + ":r:" + r + ":mid:" + mid);
            // 最后一个小于等于target的数
            if (matrix[mid / n][mid % n] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        System.out.println("l" + ":" + l + ":r:" + r);
        return matrix[l / n][l % n] == target;
    }


    public boolean searchMatrix_bst(int[][] matrix, int target) {
        // 从[0][n-1] 第一行最后一个位置向前搜索
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0;
        int y = n - 1;
        while (x < n && y > -1 && matrix[x][y] != target) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                x++;
            }
        }
        return x < n && y >= 0 && matrix[x][y] == target;
    }


}
